Typical DP Contest A -


TLE
import itertools
n = int(input())
p = list(map(int, input().split()))
ans = set()
for i in itertools.product([0, 1], repeat=len(p)):
res = 0
for idx, j in enumerate(i):
if j:
res += p[idx]
ans.add(res)
print(len(ans))

WA
n = int(input())
p = list(map(int, input().split()))
dp = [0 for _ in range(10**5)]
dp[0] = 1
for i in p:
dp[i] = 1
# 使
# for i in p:
# for j in range(10**5):
# if dp[j] and i + j < 10**5:
# dp[j+i] = 1
print(dp[:15])


n = int(input())
p = list(map(int, input().split()))
dp = [0] * 10001
dp[0] = 1
# p
for v in p:
for i in range(10001 - v, -1, -1): #
if dp[i]:
dp[i + v] = 1
# print(dp)
# [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0,
print(sum(dp))